package SubjectBacktracking.Two;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {

/**
 * 难度：中等
 * 
 * 39. 组合总和
 * 	给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * 	candidates 中的数字可以无限制重复被选取。
 * 	
 * 说明：
 * 	所有数字（包括 target）都是正整数。
 * 	解集不能包含重复的组合。 
 * 	
 * 示例 1：
 * 	输入：candidates = [2,3,6,7], target = 7,
 * 	所求解集为：
 * 	[
 * 	  [7],
 * 	  [2,2,3]
 * 	]
 * 	
 * 示例 2：
 * 	输入：candidates = [2,3,5], target = 8,
 * 	所求解集为：
 * 	[
 * 	  [2,2,2,2],
 * 	  [2,3,3],
 * 	  [3,5]
 * 	]
 * 	
 * 提示：
 * 	1 <= candidates.length <= 30
 * 	1 <= candidates[i] <= 200
 * 	candidate 中的每个元素都是独一无二的。
 * 	1 <= target <= 500
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CombinationSum cs = new CombinationSum();
		System.out.println(cs.combinationSum(new int[] {2,3,6,7}, 7));
	}

	List<List<Integer>> result = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates);	// 剪枝操作:需要排序
		backtracking(candidates, target, 0);
		return result;
    }
	public void backtracking(int[] candidates, int target, int startIndex) {
		if(target == 0) {
			result.add(new ArrayList<>(path));
			return;
		}else if(target < 0) {
			return;
		}
		// 剪枝操作:candidates[i]<=target,取出的数大于目标值则不进入循环
		for(int i=startIndex;i<candidates.length && candidates[i]<=target;i++) {
			path.add(candidates[i]);
			backtracking(candidates, target - candidates[i], i); // 关键点:不用i+1了，表示可以重复读取当前的数
			path.remove(path.size()-1);
		}
	}
}
